package com.zdp.leetcode;

import java.util.Stack;

/*
* 题目描述：
* 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 按奇偶排序数组 {
    public int[] sortArrayByParityII(int[] A) {
        int i=0;
        int j=1;
        int [] result = new int[A.length];
        for(int a:A){
            if(a%2==0){
                result[i]=a;
                i+=2;
            }else{
                result[j]=a;
                j+=2;
            }
        }
        return result;
    }
    //也可以直接在数组中交换  降低空间复杂度
    public int[] sortArrayByParityII1(int[] A) {
        int i=0,j=1;
        for(;i<A.length;i+=2){
            if(A[i]%2!=0){
                //找到奇位置上 是偶数的索引，进行交换
                //因为题目给的数据 是一半奇数 一半偶数 所以说 一旦有一个偶数不在偶坐标上，说明一定有一个奇数不在奇坐标上
                while(A[j]%2!=0)
                    j++;
                int temp  = A[i];
                A[i] = A[j];
                A[j] = A[i];
            }
        }

        return A;
    }
    //看到别人 用栈的思路  ===> 因为要操作栈 所以时间会变慢，但只需要遍历一次数组即可
    //思路就是 遇到不符合规定的数 ，如果栈都没有可以跟其交换的数，就将当前这个不符合规定的数的下标入栈
    //如果 栈中有可以跟其交换的数，就将栈顶元素出栈，与当前数进行交换
    public int[] sortArrayByParityII2(int[] A) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<A.length;i++){
            if(i%2==0&&A[i]%2!=0){
                if(stack.empty()||stack.peek()%2==0){
                    stack.push(i);
                }else{
                    swap(A,i,stack.pop());
                }
            }else if(i%2!=0&&A[i]%2==0){
                if(stack.empty()||stack.peek()%2!=0){
                    stack.push(i);
                }else{
                    swap(A,i,stack.pop());
                }
            }
        }
        return A;
    }
    public void swap(int[] A,int a,int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }

}
